<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>BFS</title>
  </head>
  <body>
    <h1>
      深度优先遍历（Depth-First
      Search，DFS）是一种重要的树/图遍历算法，它以"尽可能深"的方式探索数据结构。
    </h1>
    <script>
    const tree = {
        name: "A",
        children: [
          {
            name: "B",
            children: [{ name: "E" }, { name: "F" }],
          },
          { name: "C" },
          {
            name: "D",
            children: [{ name: "G" }, { name: "H" }],
          },
        ],
      };
      function preOrderDFS(node) {
        if (!node) return;

        console.log(node.name); // 先访问当前节点
        if (node.children) {
          for (const child of node.children) {
            preOrderDFS(child); // 递归访问子节点
          }
        }
      }
      console.log("-----------------------");
      console.log("先序遍历 - 递归实现");
      preOrderDFS(tree);

      function preOrderDFSIterative(root) {
        if (!root) return;
        const stack = [root]; // 初始化栈
        while (stack.length > 0) {
          const node = stack.pop(); // 弹出栈顶节点
          console.log(node.name); // 访问该节点
          // 将子节点逆序压栈（保证顺序正确）
          if (node.children) {
            for (let i = node.children.length - 1; i >= 0; i--) {
              stack.push(node.children[i]);
            }
          }
        }
      }
      console.log("先序遍历 - 迭代实现(使用栈)");
      preOrderDFSIterative(tree);

      function inOrderDFS(node) {
        if (!node) return;

        if (node.children) {
          if (node.children.length > 0) {
            inOrderDFS(node.children[0]); // 先访问第一个子节点
          }
        }

        console.log(node.name); // 访问当前节点

        // 访问剩余子节点
        if (node.children) {
          for (let i = 1; i < node.children.length; i++) {
            inOrderDFS(node.children[i]);
          }
        }
      }
      console.log("-----------------------");
      console.log("中序遍历");
      inOrderDFS(tree);

      function postOrderDFS(node) {
        if (!node) return;

        if (node.children) {
          for (const child of node.children) {
            postOrderDFS(child); // 递归访问子节点
          }
        }

        console.log(node.name); // 最后访问当前节点
      }
      console.log("-----------------------");
      console.log("后序遍历 - 递归实现");
      postOrderDFS(tree);

      function postOrderDFSIterative(root) {
        if (!root) return;

        const stack = [root];
        const output = [];

        while (stack.length) {
          const node = stack.pop();
          output.push(node.name);

          // 将子节点顺序压栈（保证逆序弹出）
          if (node.children) {
            for (const child of node.children) {
              stack.push(child);
            }
          }
        }

        // 反转输出结果
        while (output.length) {
          console.log(output.pop());
        }
      }
      console.log("后序遍历 - 迭代实现（使用栈）");
      postOrderDFSIterative(tree);
    </script>
  </body>
</html>
